package J.算法.滑动窗口;

import java.util.HashMap;
import java.util.Map;

public class _76_最小覆盖子串 {
    public String minWindow(String s, String t) {
        if (s.length()<t.length()){
            return "";
        }

        Map<Character,Integer> window = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();
        for (int i=0;i<t.length();i++){
            need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1);
        }

        int left=0,right =0;
        int valid=0;//表现已经匹配完成的字符
        int minLen=Integer.MAX_VALUE,start=0;

        while (right <s.length()){
            //窗口扩大
            char in = s.charAt(right);
            right++;

            //扩大后窗口更新
            if (need.containsKey(in)){
                window.put(in,window.getOrDefault(in,0)+1);
                if (need.get(in).equals(window.get(in))){
                    valid++;
                }
            }

            //缩小
            while (valid == need.size()){
                //获取最终数据
                if (right- left < minLen){
                    start = left;
                    minLen = right- left;
                }
                //开始所范围
                char out = s.charAt(left);
                left++;
                //缩小后窗口更新
                if (need.containsKey(out)){
                    //当窗某个元素多于need中的数字时
                    if (need.get(out) == window.get(out)){
                        valid--;

                    }
                    window.put(out,window.getOrDefault(out,1)-1);
                }


            }

        }

        return s.substring(start,start+minLen);




    }
}
